// 二分查找

// 循环
function binarySearch1(arr: number[], target: number): number {
    const length = arr.length;
    if (length === 0) return -1

    let startIndex = 0; //开始位置
    let endIndex = length - 1;// 结束位置

    while (startIndex <= endIndex) {

        const midIndex = Math.floor((startIndex + endIndex) / 2)

        const midValue = arr[midIndex]
        if (target < midValue) {
            // 目标值较小 则继续在左侧查找
            endIndex = midIndex - 1;
        } else if (target > midValue) {
            // 目标值较大 则继续在右侧查找
            startIndex = midIndex + 1
        } else {
            return midIndex
        }
    }
    return -1
}

// 递归

function binarySearch2(arr: number[], target: number, startIndex?: number, endIndex?: number): number {
    const length = arr.length;
    if (length === 0) return -1

    // 开始和结束的范围
    if (startIndex == null) startIndex = 0
    if (endIndex == null) endIndex = length - 1

    // 如果 statr 和 end 相遇 则结束
    if (startIndex > endIndex) return -1

    const midIndex = Math.floor((startIndex + endIndex) / 2)
    const midValue = arr[midIndex]

    if (target < midValue) {
        // 目标值较小 则继续在左侧查找
        return binarySearch2(arr, target, startIndex, midIndex - 1)
    } else if (target > midValue) {
        // 目标值较大 则继续在右侧查找
        return binarySearch2(arr, target, midIndex + 1, endIndex)
    } else {
        return midIndex
    }
}   


const arr = [10, 20, 30, 40, 50];
const target = 20;
console.log(binarySearch1(arr, target));